Повезан граф који садржи \(n\) чворова и \(n-1\) грана се назива дрво. Сваки чвор дрвета може бити његов корен. Напиши програм који за дато дрво и дати корен одређује смер свих грана у том коренском дрвету.

Улаз

Са стандардног улаза се уноси број чворова \(n\) (\(1 \leq n \leq 10^5\)), а затим и опис \(n-1\) грана дрвета. Свака грана је одређена бројевима полазног и завршног чвора (цели бројеви између \(0\) и \(n-1\)), при чему су они задати у произвољном редоследу. У последњем реду се налази редни број корена (број између \(0\) и \(n-1\)).

Излаз

На стандардни излаз треба исписати гране резултујућег коренског дрвета, при чему свака грана треба да буде оријентисана у смеру од корена ка листовима. Низ свих грана (парова бројева) треба да буде лексикографски сортиран (гране се пореде прво по првом, а затим по другом чвору).

Пример 1

Улаз

5
1 0
2 4
3 4
4 1
4

Излаз

1 0
4 1
4 2
4 3

Пример 2

Улаз

5
1 0
2 4
3 4
4 1
2

Излаз

1 0
2 4
4 1
4 3

Објашњење